package com.learning.algorithm.sort.simpleSort;

import com.learning.algorithm.sort.ArraysUtil;
import com.learning.algorithm.sort.CheckSort;
import com.learning.algorithm.sort.IntArraySort;

import java.util.Arrays;

/**
 * @Author: lishi
 * @Description: 冒泡排序
 * @Date: 2021/11/19 9:34
 */
public class BubblingSort implements IntArraySort {
    /**
     * 简单冒泡排序
     *
     * @param arrays
     */
    public static void bubblingSort(int[] arrays) {
        int loopCounts = 1;
//        System.out.println("原始数组 ： " + Arrays.toString(arrays));
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 1; j < arrays.length - i; j++) {
                if (arrays[j - 1] > arrays[j]) {
                    ArraysUtil.swap(arrays, j - 1, j);
                }
            }
//            System.out.println("第" + (i + 1) + "次排序后的数组 ： " + Arrays.toString(arrays));
            loopCounts++;
        }
//        System.out.println("bubblingSort 一起循环了" + loopCounts + "次");
    }

    /**
     * 优化冒泡排序
     * 记录每次遍历最后一次交换元素的位置，
     * 如果有一次遍历没有交换或者只交换第一、二个元素位置，说明已经是有序的数组
     *
     * @param arrays
     */
    public static void bubblingSort2(int[] arrays) {
        int loopCounts = 1;
        for (int i = 0; i < arrays.length - 1; i++) {
            int swapPos = 1;
            for (int j = 1; j < arrays.length - i; j++) {
                if (arrays[j - 1] > arrays[j]) {
                    ArraysUtil.swap(arrays, j - 1, j);
                    swapPos = j;
                }
            }
//            System.out.println("第" + (i + 1) + "次排序后的数组 ： " + Arrays.toString(arrays));
            if (swapPos == 1) {
                break;
            }
            loopCounts++;
        }
//        System.out.println("bubblingSort2 一起循环了" + loopCounts + "次");
    }

    /**
     * 优化冒泡排序
     * 在记录交换位置的基础上双向冒泡
     *
     * @param arrays
     */
    public static void bubblingSort3(int[] arrays) {
        int loopCounts = 1;
//        System.out.println("原始数组 ： " + Arrays.toString(arrays));
        for (int i = 0; i < arrays.length / 2; i++) {
            int minSwapPos = arrays.length - (2 + i);
            int maxSwapPost = 1 + i;

            //最大数冒泡
            for (int j = i + 1; j < arrays.length - i; j++) {
                if (arrays[j - 1] > arrays[j]) {
                    ArraysUtil.swap(arrays, j - 1, j);
                    maxSwapPost = j;
                }
            }
//            System.out.println("第" + (i + 1) + "次最大冒泡后的数组 ： " + Arrays.toString(arrays));
            if (maxSwapPost == (1 + i)) {
                break;
            }

            //最小数冒泡
            for (int j = arrays.length - (2 + i); j >= i; j--) {
                if (arrays[j + 1] < arrays[j]) {
                    ArraysUtil.swap(arrays, j + 1, j);
                    minSwapPos = j;
                }
            }
//            System.out.println("第" + (i + 1) + "次最小冒泡后的数组 ： " + Arrays.toString(arrays));
            if (minSwapPos == arrays.length - (2 + i)) {
                break;
            }
            loopCounts++;
        }
//        System.out.println("bubblingSort3 一起循环了" + loopCounts + "次");
    }

    public static void main(String[] args) {
        int arrayLength = 100000;
        int[] originArrays = ArraysUtil.genNoDuplicateIntArray(arrayLength);
        int[] cloneArrays = new int[arrayLength];
        System.arraycopy(originArrays, 0, cloneArrays, 0, arrayLength);
        bubblingSort3(cloneArrays);
        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays));
    }

    public int[] sort(int[] arrays) {
        bubblingSort(arrays);
        return arrays;
    }

    public String getDesc() {
        return "冒泡排序";
    }
}
